package symbolTable.seniorST;


public class LinearProbingHashST<Key, Value> {
    private int N;
    private int M = 16;
    private Key[] keys;
    private Value[] values;

    public LinearProbingHashST() {
        keys = (Key[]) new Object[M];
        values = (Value[]) new Object[M];
    }

    public LinearProbingHashST(int M) {
        this.M = M;
        keys = (Key[]) new Object[M];
        values = (Value[]) new Object[M];
    }

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    private void resize(int cap) {
        LinearProbingHashST<Key, Value> t = new LinearProbingHashST<>(cap);
        for (int i = 0; i < M; i++) {
            if (keys[i] != null)
                t.put(keys[i], values[i]);
        }
        this.keys = t.keys;
        this.values = t.values;
        this.M = t.M;
    }

    private boolean contain(Key key) {
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key))
                return true;
        return false;
    }

    public void put(Key key, Value val) {
        if (M <= 2 * N)
            resize(2 * M);
        int i;
        // 注意i = (i + 1) % M不是i++
        for (i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key)) {
                values[i] = val;
                return;
            }
        keys[i] = key;
        values[i] = val;
        N++;
    }

    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key))
                return values[i];
        }
        return null;
    }

    public void delete(Key key) {
        if (!contain(key))
            return;
        int i = hash(key);
        while (!keys[i].equals(key)) {
            i = (i + 1) % M;
        }
        keys[i] = null;
        values[i] = null;
        i = (i + 1) % M;
        while (keys[i] != null) {
            Key k = keys[i];
            Value v = values[i];
            keys[i] = null;
            values[i] = null;
            N--;
            put(k, v);
            i = (i + 1) % M;
        }
        N--;

        if (N > 0 && M >= 8 * N)
            resize(M / 2);
    }
}
